package exampleQuestions;

import java.util.Stack;

public class FindKthNodeInBST {
	
	static class Node {

		int val;
		Node left, right;
		
		public Node(int v) {
			this.val = v;
		}
		
	}

	/**
	 */
	public static void main(String[] args) {

		Node root = new Node(6);

		Node n1 = new Node(5);
		Node n2 = new Node(4);
		Node n3 = new Node(3);
		Node n4 = new Node(2);
		Node n5 = new Node(0);

		Node n6 = new Node(8);
		Node n7 = new Node(9);
		Node n8 = new Node(14);

		root.left = n3;
		root.right = n7;

		n7.right = n8;
		n7.left = n6;

		n3.left = n5;
		n5.right = n4;
		n3.right = n1;
		n3.left = n4;
		
		System.out.println(getKthNode(root, 3).val);
		
	}

	private static Node getKthNode(Node root, int k) {
		
		int current = 0;
		Stack<Node> stack1 = new Stack<Node>();
		Stack<Node> stack2 = new Stack<Node>();
		Node result = null;
		
		if(root != null) {
			stack1.push(root);
			
			while(!stack1.empty() || !stack2.isEmpty()) {
				if(!stack1.isEmpty()) {
					Node n = stack1.pop();
					if(n.right != null) {
						stack1.push(n.right);
					}
					stack2.push(n);
				} else {
					Node n = stack2.pop();
					current++;
					if(current == k) {
						result = n;
						break;
					}
					if (n.left != null) {
						stack1.push(n.left);
					}
				}
			}
		}
		
		return result;
	}

}
